1. Field
An embodiment of the invention relates to the field of decoding in digital communications.
2. Background Information
A problem often encountered in communication systems is that errors may be introduced into the information that is transmitted over the communication link. Noise is a common contributing cause of the errors. A representative form of noise that may be expected is additive white Gaussian noise (AWGN), sometimes referred to in the arts simply as white noise. The white noise may potentially alter the characteristics of the carrier wave used to relay the modulated information. Such alteration of the carrier wave may cause the receiver to make errors when interpreting the received information. In a wireless communication system, such errors may be compounded by a generally low signal-to-noise ratio at the receiver, particularly when there is a large geographic distance between the transmitter and the receiver. Faulty equipment and other imperfections in the communication link may also contribute to the introduction of errors.
In the case of digital data, the noise may cause bit errors in which an information bit may be flipped. For example, a “1” may be flipped to a “0”, or a “0” may be flipped to a “1”. To further illustrate, a transmitter may transmit digital data (e.g., . . . 10110 . . . ) to a receiver, and the receiver may receive erroneous data (e.g., . . . 10111 . . . , where the error involves the last bit of the transmitted data being “flipped” from a “0” to a “1”). Such errors, if left uncorrected, may be problematic.
Traditionally, a variety of error correction techniques have been employed to help identify and eliminate the errors. A common form of error correction technique for digital data streams is Forward Error Correction (FEC). Employing FEC may allow the receiver to identify the error (e.g., the flipped bit in the sequence . . . 10111 . . . ) and correct the error, by flipping the erroneous bit (e.g., to produce the original digital data . . . 10110 . . . ).
One of the more prevalent FEC techniques is convolutional encoding with trellis decoding. This technique is supported by numerous communications standards, including, but not limited to, ADSL and SHDSL broadband standards. Convolutional encoding may involve using sophisticated mathematical encoding algorithms or other logic to add redundant channel coding information to the information of interest. The redundant information may allow a receiver to detect and correct potential errors due to noise or other imperfections. The receiver may employ trellis decoding, for example Viterbi decoding, in order to interpret the encoded information, and to identify and eliminate the errors.
The inventor has recognized that complex logic has heretofore generally been needed in order to perform the trellis or Viterbi decoding. The complex logic tends to increase the time needed to design and validate decoders. Additionally, the complex logic tends to increase the physical size and cost of the decoders, and decrease the operating speed of the decoders.